Any point (server, laptop computer, a network-ready device, a wireless hand-held device, etc.) can establish a communication link via the Internet with another point and data can be exchanged between these two points. The exchanged data can be a short text message, a document, or a multi-media object, and even streaming audio/video. It is difficult to know how traffic may flow between two selected points on the Internet at a given time. In an ideal situation, we would simply log into one of the endpoints, run a traceroute to the other location (or perform a similar procedure), and observe the path traffic takes. Then we would repeat the experiment in reverse to observe the opposite (and not necessarily symmetric) path. Typically, however, one cannot log into just any Internet point and run such measurements.
The data traffic from one endpoint to another generally flows via systems (routers, cables, wireless links, etc.) of one or more Autonomous Systems (AS). A pair of points on the Internet may communicate with each other via one or more AS's. When the communication occurs via two or more AS's, a physical (electrical) connectivity between those AS's is required but is usually not adequate; a contractual relationship must also exist between those AS's
An estimate of the path to be taken by traffic between two points can, however, be useful in several ways. A user may be able obtain estimates of various traffic characteristics such as average delay, delay jitter, reliability of the connection, etc. Furthermore, in some situations a user at one endpoint can choose between feasible alternate paths to the other endpoint. That decision can be informed by the knowledge of the expected traffic characteristics, that can change from time to time. Some techniques allow for estimation of various traffic characteristics when an actual, router-level path between the points of interest is provided. These methods are not applicable, however, when the actual router-level paths are not provided. Therefore, there is a need for a technique that can efficiently predict a path between two endpoints on the Internet. There is also a need for techniques that can estimate various traffic characteristics without relying on the knowledge of actual router-level paths.